• Asymptotic analysis 漸進分析
• 保持持續討論的態度，asymptotic analysis 是討論不同解法彼此之間的 trade off，所以其實沒有一個完全正確的解法，重點在於不同解法之間的優劣。

來看個例子

int example(int n) {
    for(int i=0; i<10; i++) {
        //do O(1) work
    }
}

在這個例子中，不管 n 如何改變 ...n=1000、n=100000000，結果都會保持 constant，所以他的曲線或者 paramater 就會像是 O(1)

接下來來看一些 O(n) 的例子

int example(int n) {
    for(int i=0; i<n; i++) {
        //do O(1) work
    }
}

int example(int n) {
    for(int i=0; i<2n; i++) {
        //do O(1) work
    }
}

上面兩個例子，可以清楚的看出來當 n 變大時，會影響運行的次數，呈現 linear 的 parameter，而且第二個例子的斜率更大，但我們其實比較看重不同 parameter 的變化模式，所以可以都簡略為 O(n)。

Asymptotic Bounding 101

如何判斷好壞

• 通常要判斷一個演算法，我們可能會分為 best 、 average、worst
• 下面會可以用一些指標來表達多好、多壞、範圍等

  O() -> bigO //Upper bound，越高，演算法越沒效率
  o() -> little o
  Θ( ) -> theta //exact bound
  Ω( ) -> big omega //越高，演算法越有效率
  ω( ) -> little omega

更深入的談 asymptotic bounding

來看一段關於 asymptotic 的數學演示，展示如何逼近 upper bound

T(n)
is O(f(n)) "if"
T(n) <= C*O(f(n))
for all n>= n

接下來我們假若把 T(n) 的曲線畫出來，然後試試用 O(n)、O(n2)、log(n) 來逼近，會發現只有 linear 的 O(n) 可以無窮逼近 T(n)，所以這時候我們就不會在意 C (constant) 是如何變化，因為只有在選對 "模式" 的狀態下，才能逼近正確的 T(n)